package me.mingshan.leetcode;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @author hanjuntao
 * @date 2025/8/28 0028
 */
public class L_671_二叉树中第二小的节点 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        System.out.println(findSecondMinimumValue2(root));
    }

    /**
     * 1. 使用优先级队列 和set
     * 2. 遍历二叉树，判断set是否有值，没有值将元素加到优先级队列，保持堆的大小小于等于
     * 3. 检测优先级队列中堆的大小是否大于1，大于1则弹出堆顶元素，否则返回-1
     *
     * @param root
     * @return
     */
    public static int findSecondMinimumValue(TreeNode root) {
        if (root == null) {
            return -1;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        HashSet<Integer> set = new HashSet<>();

        pre(root, priorityQueue, set);

        return priorityQueue.size() > 1 ? priorityQueue.poll() : -1;
    }

    private static void pre(TreeNode root, PriorityQueue<Integer> priorityQueue, Set<Integer> set) {
        if (root == null) {
            return;
        }

        if (!set.contains(root.val)) {
            priorityQueue.add(root.val);
            if (priorityQueue.size() > 2) {
                priorityQueue.poll();
            }

            set.add(root.val);
        }

        pre(root.left, priorityQueue, set);
        pre(root.right, priorityQueue, set);
    }

    /**
     * 1. 递归
     *
     * 从题意可知，任意一个树，其根节点的值，必须小于等于子树的值
     *
     * 换句话说，只需要找到树中比根节点值大的最小值
     *
     *
     * @param root
     * @return
     */
    public static int findSecondMinimumValue2(TreeNode root) {
        return finMinGtRootValue(root, root.val);
    }

    private static int finMinGtRootValue(TreeNode node, int val) {
        if (node == null) {
            return -1;
        }

        // 如果当前节点值大于目标值，直接返回当前值（因为子树中所有值都大于等于当前值）
        if (node.val > val) {
            return node.val;
        }

        // 然后递归找子树大于目标值的最小值
        int leftMin = finMinGtRootValue(node.left, val);
        int rightMin = finMinGtRootValue(node.right, val);

        if (leftMin != -1 && rightMin != -1) {
            return Math.min(leftMin, rightMin);
        } else if (leftMin != -1) {
            return leftMin;
        } else {
            return rightMin;
        }
    }
}
